package com.practice.niuke.new_direct_practice.class32;

/**
 * （有一个数组，长度为N，有一个窗口长度为M，M在N上滑动（每次进一个数，出一个数），求滑动到形成的中位数轨迹）
 * Median is the middle value in an ordered integer list. If the size of the list is
 * even, there is no middle value. So the median is the mean of the two middle value.
 * Examples:
 * [2,3,4] , the median is 3
 * [2,3], the median is (2 + 3) / 2 = 2.5
 * Given an array nums, there is a sliding window of size k which is moving from the
 * very left of the array to the very right. You can only see the k numbers in the
 * window. Each time the sliding window moves right by one position. Your job is to
 * output the median array for each window in the original array.
 * For example,
 * Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.
 * Window position Median
 * --------------- -----
 * [1 3 -1] -3 5 3 6 7 1
 * 1 [3 -1 -3] 5 3 6 7 -1
 * 1 3 [-1 -3 5] 3 6 7 -1
 * 1 3 -1 [-3 5 3] 6 7 3
 * 1 3 -1 -3 [5 3 6] 7 5
 * 1 3 -1 -3 5 [3 6 7] 6
 * Therefore, return the median sliding window as [1,-1,-1,3,5,6].
 */
public class Code02_SlidingWindowMedian {

	/**
	 * SB树的节点
	 */
	public static class SBTNode<K extends Comparable<K>> {
		public K key;
		public SBTNode<K> l;
		public SBTNode<K> r;
		public int size;

		public SBTNode(K k) {
			key = k;
			size = 1;
		}
	}

	/**
	 * 自定义有序表
	 *
	 * @param <K>
	 */
	public static class SizeBalancedTreeMap<K extends Comparable<K>> {
		private SBTNode<K> root;

		/**
		 * 右旋
		 *
		 * @param cur
		 * @return
		 */
		private SBTNode<K> rightRotate(SBTNode<K> cur) {
			SBTNode<K> leftNode = cur.l;
			cur.l = leftNode.r;
			leftNode.r = cur;
			leftNode.size = cur.size;
			cur.size = (cur.l != null ? cur.l.size : 0) + (cur.r != null ? cur.r.size : 0) + 1;
			return leftNode;
		}

		/**
		 * 左旋
		 *
		 * @param cur
		 * @return
		 */
		private SBTNode<K> leftRotate(SBTNode<K> cur) {
			SBTNode<K> rightNode = cur.r;
			cur.r = rightNode.l;
			rightNode.l = cur;
			rightNode.size = cur.size;
			cur.size = (cur.l != null ? cur.l.size : 0) + (cur.r != null ? cur.r.size : 0) + 1;
			return rightNode;
		}

		/**
		 * 维持平衡性
		 *
		 * @param cur
		 * @return
		 */
		private SBTNode<K> matain(SBTNode<K> cur) {
			if (cur == null) {
				return null;
			}
			if (cur.l != null && cur.l.l != null && cur.r != null && cur.l.l.size > cur.r.size) {
				cur = rightRotate(cur);
				cur.r = matain(cur.r);
				cur = matain(cur);
			} else if (cur.l != null && cur.l.r != null && cur.r != null && cur.l.r.size > cur.r.size) {
				cur.l = leftRotate(cur.l);
				cur = rightRotate(cur);
				cur.l = matain(cur.l);
				cur.r = matain(cur.r);
				cur = matain(cur);
			} else if (cur.r != null && cur.r.r != null && cur.l != null && cur.r.r.size > cur.l.size) {
				cur = leftRotate(cur);
				cur.l = matain(cur.l);
				cur = matain(cur);
			} else if (cur.r != null && cur.r.l != null && cur.l != null && cur.r.l.size > cur.l.size) {
				cur.r = rightRotate(cur.r);
				cur = leftRotate(cur);
				cur.l = matain(cur.l);
				cur.r = matain(cur.r);
				cur = matain(cur);
			}
			return cur;
		}

		/**
		 * 查询最后一个位置的key
		 *
		 * @param key
		 * @return
		 */
		private SBTNode<K> findLastIndex(K key) {
			SBTNode<K> pre = root;
			SBTNode<K> cur = root;
			while (cur != null) {
				pre = cur;
				if (key.compareTo(cur.key) == 0) {
					break;
				} else if (key.compareTo(cur.key) < 0) {
					cur = cur.l;
				} else {
					cur = cur.r;
				}
			}
			return pre;
		}

		private SBTNode<K> add(SBTNode<K> cur, K key) {
			if (cur == null) {
				return new SBTNode<K>(key);
			} else {
				// 此处的size为本题特有的，标准有序表中没有
				cur.size++;
				if (key.compareTo(cur.key) < 0) {
					cur.l = add(cur.l, key);
				} else {
					cur.r = add(cur.r, key);
				}
				return matain(cur);
			}
		}

		private SBTNode<K> delete(SBTNode<K> cur, K key) {
			cur.size--;
			if (key.compareTo(cur.key) > 0) {
				cur.r = delete(cur.r, key);
			} else if (key.compareTo(cur.key) < 0) {
				cur.l = delete(cur.l, key);
			} else {
				if (cur.l == null && cur.r == null) {
					// free cur memory -> C++
					cur = null;
				} else if (cur.l == null && cur.r != null) {
					// free cur memory -> C++
					cur = cur.r;
				} else if (cur.l != null && cur.r == null) {
					// free cur memory -> C++
					cur = cur.l;
				} else {
					SBTNode<K> pre = null;
					SBTNode<K> des = cur.r;
					des.size--;
					while (des.l != null) {
						pre = des;
						des = des.l;
						des.size--;
					}
					if (pre != null) {
						pre.l = des.r;
						des.r = cur.r;
					}
					des.l = cur.l;
					des.size = des.l.size + (des.r == null ? 0 : des.r.size) + 1;
					// free cur memory -> C++
					cur = des;
				}
			}
			return cur;
		}

		/**
		 * 得到位于kth位置的key
		 *
		 * @param cur
		 * @param kth
		 * @return
		 */
		private SBTNode<K> getIndex(SBTNode<K> cur, int kth) {
			if (kth == (cur.l != null ? cur.l.size : 0) + 1) {
				return cur;
			} else if (kth <= (cur.l != null ? cur.l.size : 0)) {
				return getIndex(cur.l, kth);
			} else {
				return getIndex(cur.r, kth - (cur.l != null ? cur.l.size : 0) - 1);
			}
		}

		public int size() {
			return root == null ? 0 : root.size;
		}

		public boolean containsKey(K key) {
			if (key == null) {
				throw new RuntimeException("invalid parameter.");
			}
			SBTNode<K> lastNode = findLastIndex(key);
			return lastNode != null && key.compareTo(lastNode.key) == 0 ? true : false;
		}

		public void add(K key) {
			if (key == null) {
				throw new RuntimeException("invalid parameter.");
			}
			SBTNode<K> lastNode = findLastIndex(key);
			if (lastNode == null || key.compareTo(lastNode.key) != 0) {
				root = add(root, key);
			}
		}

		public void remove(K key) {
			if (key == null) {
				throw new RuntimeException("invalid parameter.");
			}
			if (containsKey(key)) {
				root = delete(root, key);
			}
		}

		public K getIndexKey(int index) {
			if (index < 0 || index >= this.size()) {
				throw new RuntimeException("invalid parameter.");
			}
			return getIndex(root, index + 1).key;
		}

	}

	public static class Node implements Comparable<Node> {
		public int index;
		public int value;

		public Node(int i, int v) {
			index = i;
			value = v;
		}

		@Override
		public int compareTo(Node o) {
			return value != o.value ? Integer.valueOf(value).compareTo(o.value)
					: Integer.valueOf(index).compareTo(o.index);
		}
	}

	/**
	 * 题目解法（TODO：第31章视频中讲解的方法）
	 *
	 * @param nums
	 * @param k
	 * @return
	 */
	public static double[] medianSlidingWindow(int[] nums, int k) {
		// 自定义有序表
		SizeBalancedTreeMap<Node> map = new SizeBalancedTreeMap<>();
		for (int i = 0; i < k - 1; i++) {
			map.add(new Node(i, nums[i]));
		}
		double[] ans = new double[nums.length - k + 1];
		int index = 0;
		for (int i = k - 1; i < nums.length; i++) {
			map.add(new Node(i, nums[i]));
			if (map.size() % 2 == 0) {
				Node upmid = map.getIndexKey(map.size() / 2 - 1);
				Node downmid = map.getIndexKey(map.size() / 2);
				ans[index++] = ((double) upmid.value + (double) downmid.value) / 2;
			} else {
				Node mid = map.getIndexKey(map.size() / 2);
				ans[index++] = (double) mid.value;
			}
			map.remove(new Node(i - k + 1, nums[i - k + 1]));
		}
		return ans;
	}

}
